package al03slideWindow;

import java.util.*;

public class findAnagrams {
    public static List<Integer> findAnagrams(String s, String p) {

        ArrayList<Integer> list = new ArrayList<>();


        int[] pFrequency = new int[26];
        int[] sFrequency = new int[26];

        for(char c : p.toCharArray()){
            pFrequency[c-'a']++;
        }


        for(int i = 0;i<s.length();i++){
            sFrequency[s.charAt(i)-'a']++;

            if(i>= p.length()){
                sFrequency[s.charAt(i-p.length())-'a']--;
            }

            if(Arrays.equals(pFrequency,sFrequency)){
                list.add(i - p.length() + 1);
            }
        }

        return list;
    }


    public static void main(String[] args) {
       // 示例 1
        String s1 = "cbaebabacd";
        String p1 = "abc";
        System.out.println(findAnagrams(s1, p1));  // 输出：[0, 6]

/*         // 示例 2
        String s2 = "abab";
        String p2 = "ab";
        System.out.println(findAnagrams(s2, p2));  // 输出：[0, 1, 2]*/



        // 示例 4
        String s4 = "dddddd";
        String p4 = "dd";
        System.out.println(findAnagrams(s4, p4));  // 输出：[0, 1, 2, 3, 4]

        // 示例 5
        String s5 = "aaa";
        String p5 = "aa";
        System.out.println(findAnagrams(s5, p5));  // 输出：[0, 1]

        // 示例 6
        String s6 = "abcd";
        String p6 = "xyz";
        System.out.println(findAnagrams(s6, p6));  // 输出：[]

        // 示例 7
        String s7 = "mississippi";
        String p7 = "ssi";
        System.out.println(findAnagrams(s7, p7));  // 输出：[1, 2, 3, 4, 5]

        // 示例 8
        String s8 = "abcabcabc";
        String p8 = "abc";
        System.out.println(findAnagrams(s8, p8));  // 输出：[0, 1, 2, 3, 4, 5, 6]
    }
}
